package string;

import java.util.*;

public class StringMain {

    
    public static void main(String[] args) {
        String str1 = "abcdefg";
        String str2 = "cdeg";
        System.out.println(getLongestSubString(str1,str2));
    }

    //求最长公共子串，动态规划版本   还有一种版本  打印短串全排列，然后在长串中比较
    public String findLongestCommonSubstring0(String string0,String string1) {
        int[][] answerArray = new int[string0.length()][string1.length()];
        int maxSubstringLength = 0;
        int startLongestIndex = 0;
        for (int counter = 0;counter < string0.length();counter++) {
            for (int counter0 = 0;counter0 < string1.length();counter0++) {
                if (string0.charAt(counter) == string1.charAt(counter0)) {
                    if (counter - 1 >= 0 && counter0 - 1 >= 0)answerArray[counter][counter0] = answerArray[counter - 1][counter0 - 1] + 1;
                    else answerArray[counter][counter0] = 1;
                    if (answerArray[counter][counter0] > maxSubstringLength) {
                        maxSubstringLength = answerArray[counter][counter0];
                        startLongestIndex = counter - maxSubstringLength + 1;
                    }
                } else answerArray[counter][counter0] = 0;
            }
        }
        return string0.substring(startLongestIndex,startLongestIndex + maxSubstringLength);
    }


    //找出两个字符串的最长公共子序列 dp
    public static int getLongestSubString(String str1,String str2){
        int len1= str1.length();
        int len2= str2.length();
        int[][] dp = new int[len1+1][len2+1];   //两个字符串截止i j之前最长的公共子序列长度
        for (int i=1;i<=len1;i++){
            for (int j =1;j<=len2;j++){
                if (str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }

    //返回最长回文子串
    public String longestPalindrome (String s) {
        if(s.length()<=1){
            return s;
        }
        // write code here
        int maxLen = 0;
        String res = null;
        for(int x=0;x<s.length()-1;x++){
            int[] a1 = getLongIndex(s,x,x);
            int[] a2 = getLongIndex(s,x,x+1);
            if(a1[1] - a1[0] > a2[1] - a2[0] && a1[1] - a1[0]>maxLen){
                maxLen = a1[1] - a1[0];
                res = s.substring(a1[0],a1[1]+1);
            }else if((a1[1] - a1[0] < a2[1] - a2[0]) &&( a2[1] - a2[0]>maxLen)){
                maxLen = a2[1] - a2[0];
                res = s.substring(a2[0],a2[1]+1);
            }
        }
        return res;
    }
    public static int[] getLongIndex(String s,int a,int b){
        int[] resIndex = new int[2];
        while(a>-1 && b<s.length() &&s.charAt(a) == s.charAt(b)){
            resIndex[0] = a;
            resIndex[1] = b;
            a--;
            b++;
        }
        return resIndex;
    }


    //求最长回文串的长度
    public int getLongestPalindrome(String A, int n) {
        // write code here
        int maxLen = 0;
        if(n==0||n==1){
            return n;
        }
        int res = 0;
        for(int a=0;a<n-1;a++){
            res = Math.max(res,Math.max(getLongest(A,a,a),getLongest(A,a,a+1)));
        }
        return res;

    }
    public static int getLongest(String str,int a, int b){
        int res= b==a?-1:0;
        while(a>-1 && b<str.length() && str.charAt(a) == str.charAt(b)){
            res+=2;
            a--;
            b++;
        }
        return res;
    }

    /*
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     * 解题思路：把t的所有子序列全部放在集合里 然后判断是否包含s
     * */
    public static boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c:s.toCharArray()){
            index = t.indexOf(c,index+1);  //如果不存在则会返回-1
            if (index==-1){
                return false;
            }
        }
        return true;
    }
    /*
     *给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * */
    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> set=null;
        char[] chars = s.toCharArray();
        int maxLen = 0;
        for (int a=0;a<chars.length;a++){
            set =  new HashSet<>();
            int temp = 0;
            for (int b = a;b<chars.length;b++){
                if (set.contains(chars[b])){
                    break;
                }
                set.add(chars[b]);
                temp++;
            }
            maxLen = maxLen<temp? temp :maxLen;
        }
        return maxLen;
    }


    /*
     * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,
     * 则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
     * //递归思路：每次选一个字符  + 剩下未被选中字符的全排列 就是当前全排列
     * */
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if(str == null){
            return res;
        }
        if (str.length()==1){
            res.add(str);
            return res;
        }
        HashSet<String> stringHashSet = new HashSet<>();
        for (int a=0;a<str.length();a++){
            String strs = str;
            char t= strs.charAt(a);
            for (String s: Permutation(deleteIndex(strs,a))){
                String ss = t+s;
                res.add(ss);
                stringHashSet.add(ss);
            }
        }
        return res;
    }
    public static String deleteIndex(String string,int index){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(string.toCharArray());
        stringBuilder.deleteCharAt(index);
        return stringBuilder.toString();
    }

    /*
     * 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,
     * 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
     * */
    public int FirstNotRepeatingChar(String str) {
        int res = -1;
        HashMap<Character,Integer> map = new HashMap<>();
        char[] cas = str.toCharArray();
        for (int a=0;a<cas.length;a++){
            char c = cas[a];
            int value = 0;
            if (map.keySet().contains(c)){
                value = map.get(c)+1;
            }
            map.put(c,++value);
        }
        for (int b=0;b<cas.length;b++){
            if (map.get(cas[b]) ==1){
                return b;
            }
        }
        return res;
    }

    public static void printStr(String str,int index){
        if (index<str.length() &&  str!=null) {
            printStr(str, index + 1);
            String newStr = printByLess(str, index);
            System.out.println(""+newStr);
            printStr(newStr, index);
        }
    }


    public static String printByLess(String str,int index){
        StringBuilder stringBuilder = new StringBuilder();
        if (index<str.length()) {
            char[] chars = str.toCharArray();
            for (int a = 0; a < chars.length; a++) {
                if (a != index) {
                    stringBuilder.append(chars[a]);
                }
            }
        }
        return stringBuilder.toString();
    }

}
